package EnterpriseAlgorithm.LinkedList.Code.RemoveReciprocal;

import EnterpriseAlgorithm.LinkedList.Code.ListCode.DoubleNode;
import EnterpriseAlgorithm.LinkedList.Code.ListCode.Node;

import java.util.InputMismatchException;

public class RemoveReciprocal {

    //接受一个单链表，删除指定倒数的元素，并返回头结点。
    public Node removeNthFromEnd(Node head, int n) {
        if (n < 1 || head == null) {
            throw new InputMismatchException("n is not Compliant or head is null");
        }
        //创建一个结点，充当虚拟头指针
        Node dummyNode = new Node(0);
        dummyNode.next = head;

        //创建快慢指针
        Node fastIndex = dummyNode;
        Node slowIndex = dummyNode;

        //只要快慢指针相差 n 个结点即可
        for (int i = 0; i <= n; i++) {
            fastIndex = fastIndex.next;

            // 如果 n > 链表长度,则fastIndex == null ,接下来也不会再做处理
            if (fastIndex == null) {
                //抛出异常
                throw new IndexOutOfBoundsException("n is OutOf The LinkedList.Size ");
            }
        }

        while (fastIndex != null) {
            fastIndex = fastIndex.next;
            slowIndex = slowIndex.next;
        }

        //此时 slowIndex 的位置就是待删除元素的前一个位置。
        //具体情况可自己画一个链表长度为 3 的图来模拟代码来理解
        slowIndex.next = slowIndex.next.next;
        return dummyNode.next;
    }

    // 其他方法
    public Node removeNthFromEnd_2(Node head, int n) {
        if (n < 1 || head == null) {
            throw new InputMismatchException("n is not Compliant or head is null");
        }
        Node cur = head;
        while (cur != null) { // 移动指针
            n--;
            cur = cur.next;
        }
        if (n == 0) { // 删除头节点的情况
            head = head.next;
        }
        if (n < 0) {
            cur = head;
            while (++n != 0) {
                cur = cur.next;
            }
            cur.next = cur.next.next;
        }
        // n > 0 说明 n 的长度大于链表的长度。
        return head;
    }

    public DoubleNode removeNthFromEnd_3(DoubleNode head, int n) {
        if (n < 1 || head == null) {
            throw new InputMismatchException("n is not Compliant or head is null");
        }
        DoubleNode cur = head;
        while (cur != null) { // 移动 n
            n--;
            cur = cur.next;
        }
        if (n == 0) {
            head = head.next;
            head.prev = null;  // 删掉头节点后，新的头节点prev 指向 null
        }
        if (n < 0) {
            cur = head;
            while (++n != 0) {
                cur = cur.next;
            }
            DoubleNode newNext = cur.next.next;
            cur.next = newNext;
            if (newNext != null) {  //删除最后一个的情况
                newNext.prev = cur;
            }
        }
        return head;
    }

}
